impl Solution {
    pub fn search(arr: Vec<i32>, target: i32) -> i32 {
        if let Some(ind) = Solution::b_search(&arr[..], target) {
            ind as i32
        } else {
            -1
        }
    }
    fn b_search(arr: &[i32], target: i32) -> Option<usize> {
        if arr.len() == 0 {
            return None;
        }
        if arr.len()==1{
            if arr[0]==target{
                return Some(0)
            }else{
                return None
            }
        }
        if arr.first().unwrap() <arr.last().unwrap() {
            let  ( mut l,mut r) = (0, arr.len() - 1);
            if target<arr[l]||target>arr[r]{
                return None;
            }
            while l <=r {
                let mut mid = l + (r - l) / 2;
                if arr[mid] == target {
                    mid = loop {
                        if mid < 0 || arr[mid] != target {
                            break mid + 1;
                        }
                        mid -= 1;
                    };
                    return Some(mid as usize);
                } else if arr[mid] < target {
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
            None
        } else {
            let mut mid = arr.len() / 2;
            if let Some(ind) = Solution::b_search(&arr[..mid], target) {
                return Some(ind);
            }
            if let Some(ind) = Solution::b_search(&arr[mid..], target) {
                return Some(mid as usize + ind);
            }
            None
        }
    }
}
